//https://leetcode.cn/problems/magnetic-force-between-two-balls/submissions/564733672/

class Solution {
public:
    int maxDistance(vector<int>& v, int m) {
        sort(begin(v),end(v));
        int l = 1, r = 1e9+1, mid = 0, ans = 0x3f3f3f3f, p, cnt, n = v.size();
        auto f = [&](int x) -> bool {
            p = v[0], cnt = 1;
            for (int i = 1; i < n; i++) {
                if (v[i] - p >= x) {
                    p = v[i];
                    cnt++;
                }
            }
            return cnt >= m;
        };
        while (l <= r) {
            mid = (l+r)>>1;
            if (f(mid)) l = mid+1, ans = mid;
            else r = mid -1;
        }

        return ans;
    }
};

auto init = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 'c';
}();